<head>
    <meta charset="UTF-8">
<title>算法提高 Channel</title>
<link rel="stylesheet" href="../css/main.css">
</head>
 <p>【问题描述】<br />
Joe，一个前冠军程序员，终于买了农场。不，不，他过得很好；他只是利用了他丰富的编程比赛奖金购买了他的祖传农场。<br />
他希望退休，养奶牛度过余生(因为一些原因，他现在认为自己是一个奶牛专家)。<br />
不幸的是，农夫Joe简单的田园梦也无法实现。他的农场所在气候寒冷--对于奶牛太冷了！<br />
更糟糕的是，气候很干燥不适合种植庄稼。Joe现在意识到他必须为自己的农场制定一个灌溉方案。这个方案将使一条河穿过农场里的一条蜿蜒的渠道。由于作物在渠道旁能茁壮成长，所以渠道越长越好。<br />
他的田地是一个被划分成格子的狭长的矩形。一些格子有泥土，用&quot;.&quot;表示，或者不能移动的石头，用&quot;#&quot;表示。灌溉渠道是一个一格宽的从田地左上角进入从右下角流出。石头的格子不能通过。当然，它不能够自交，即使是在角上碰到也不行(这样水会渗透并采取更短的路径)。<br />
下面两种情况表示渠道自交：<br />
&nbsp;CCCC   C...<br />
C.C.C   CCCC<br />
CCC.C   ..CC<br />
...CC   ..C.<br />
...C.   ..C.<br />
&nbsp;...CC   ..CC<br />
（为什么不能等宽，大家自行放到等宽字体中看吧）<br />
不幸的是，Joe那最好的编程能力已经被他抛之脑后了。他有一个很简单的解决方法但是太耗时了。你能帮他找到这个渠道的最佳位置吗？<br />
【输入格式】<br />
输入包含多组数据。<br />
每个测试数据包含一个r表示行数(2&lt;=r&lt;=20)和一个c表示列数(2&lt;=c&lt;=9)。接着r行c列的一个矩阵表示他的田地。<br />
由0 0结束输入<br />
【输出格式】<br />
对于每一组数据。<br />
输出数据序号。<br />
接下来r行表示一种设置渠道的方案，保证有解。<br />
每组数据后输出一个空行。<br />
参照样例。<br />
【样例输入】<br />
3 3<br />
.#.<br />
...<br />
.#.<br />
6 7<br />
.......<br />
.......<br />
.......<br />
....#..<br />
.......<br />
.#.....<br />
0 0<br />
【样例输出】<br />
Case 1:<br />
C#.<br />
CCC<br />
.#C<br />
<br />
Case 2:<br />
CCCCCCC<br />
......C<br />
CCCCCCC<br />
C...#..<br />
CCC.CCC<br />
.#CCC.C<br />
【数据规模和约定】<br />
见输入格式。<br />
&nbsp;</p>